The present invention relates to a key distribution method and system in secure broadcast communication.
Up to now, several methods have been proposed in regard to secure broadcast communication (or key management).
For example, a copied key method disclosed by S. J. Kent, xe2x80x9cSecurity requirement and protocols for a broadcast scenarioxe2x80x9d, IEEE Trans. Commun., COM-29, 6, pp. 778-786 (1981) is fundamental. The copied key method is the simple extension of the conventional one-to-one cryptographic individual communication to a multi-address communication. The copy of one kind of key is distributed to a sender and a plurality of normal receivers. The sender enciphers information by use of the copied key and transmits the enciphered information. The normal receiver deciphers the information by use of the same copied key.
The other methods include (i) a secure broadcast communication method disclosed by K. Koyama, xe2x80x9cA Cryptosystem Using the Master Key for Multi-Address Communicationxe2x80x9d, Trans. IEICE, J65-D, 9, pp. 1151-1158 (1982) which uses a master key alternative to RSA individual key, (ii) a key distribution system disclosed by Lee et al., xe2x80x9cA Multi-Address Communication Using a Method of Multiplexing and Demultiplexingxe2x80x9d, the Proc. of the 1986 Symposium on Cryptography and Information Security, SCIS86 (1986) which is based on the multiplexing and demultiplexing of information trains using the Chinese reminder theorem, and (iii) a system disclosed by Mambo et al., xe2x80x9cEfficient Secure Broadcast Communication Systemsxe2x80x9d, IEICE Technical Report, ISEC93-34 (October 1993).
According to the system for performing the multiplexing and demultiplexing of information trains by use of the Chinese reminder theorem, the following processes are performed.
(1) Key Generating Process
For a receiver i (1xe2x89xa6ixe2x89xa6r) are generated s compromise integers g1, g2, . . . , gs (rxe2x89xa6s) and gi is distributed to the receiver i as confidential information of the receiver i beforehand.
(2) Enciphering Process
It is assumed that s information trains to be multiplexed are M1, M2, . . . , Ms. A sender calculates a multiplexed transmit sentence F in accordance with   F  =            ∑              i        =        1            k        ⁢                  A        i            ⁢              G        i            ⁢              M        i            ⁢      mod      ⁢              xe2x80x83            ⁢      G      
and makes the multi-address transmission of F, wherein G, Gi and Ai are the least integer Ai which satisfies       G    =                  ∏                  i          =          1                k            ⁢              g        i              ,
Gi=G/gi,
AiGixe2x89xa11(mod gi).
(3) Deciphering Process
The receiver i demultiplexes Mi from F by use of gi in accordance with
Mi=F mod gi
According to the system disclosed by Mambo et al., xe2x80x9cEfficient Secure Broadcast Communication Systemsxe2x80x9d, IEICE Technical Report, ISEC93-34 (October 1993), the following processes are performed.
(1) Key Generating Process
A reliable center generates the following information.
Confidential information:
P=2p+1,Q=2q+1:prime number (p,q:prime number)
eixcex5Z,0 less than ei less than L(1xe2x89xa6ixe2x89xa6m)
Public information:
xe2x80x83gxcex5Z, 0 less than g less than N
N=PQ
vi=gei mod N(1xe2x89xa6ixe2x89xa6m).
The center calculates s"sgr" satisfying       S    σ    =                    ∑                  i          =          1                k            ⁢              e                  σ          ⁡                      (            i            )                                ≡          1      ⁢              (                  mod          ⁢                      xe2x80x83                    ⁢          L                )            
for "sgr"xcex5S and distributes s"sgr" as confidential information of a receiver U"sgr", wherein set S={f|one-to-one map f: A={1, 2, . . . , k}xe2x86x92B={1, 2, . . . , m}, m greater than k}.
(2) Key Distribution Process
(i) A sender randomly selects an integer r to calculate
zi=vir mod N(1xe2x89xa6ixe2x89xa6m)
with the object of sharing a common key
K=gr mod N
in common with the receiver and makes the multi-address transmission of zi (1xe2x89xa6ixe2x89xa6m).
(ii) The receiver U"sgr" calculates the common key K in accordance with   K  =                    (                              ∏                          i              =              1                        k                    ⁢                      z                          σ              ⁡                              (                i                )                                                    )                    S        σ              ⁢    mod    ⁢          xe2x80x83        ⁢          N      .      
In the above-mentioned key distribution based on the multiplexing method using the Chinese reminder theorem, the length of key distribution data becomes large in proportion to the number of receivers since the key distribution data for individual users are transmitted in a serially arranged manner. This offers a problem from an aspect of efficiency in the case where several millions of receivers are made an object as in a broadcasting satellite service.
On the other hand, in the system disclosed by Mambo et al., xe2x80x9cEfficient Secure Broadcast Communication Systemsxe2x80x9d, IEICE Technical Report, ISEC93-34 (October 1993), the length of key distribution data can be reduced even in the case where the number of receivers is large. However, this system has a problem in security that if receivers conspire with each other, confidential information of another receiver can be calculated. Also, it is not possible to possess a key in common with only receivers which belong to any set of receivers.
Therefore, a principal object of the present invention is to provide a key distribution method and system for secure broadcast communication having the following features:
(1) receivers possess individual confidential key information to share a data enciphered key between the receivers;
(2) even in the case where the number of receivers is large, it is possible to reduce the length of key distribution data;
(3) even if receivers club their confidential information in conspiracy with each other, it is difficult to calculate key information of another receiver and confidential information of a key generator; and
(4) it is possible to possess the data enciphered key in common with only receivers which belong to any set of receivers.
To that end, a key generator generates a finite set S including a plurality of confidential information of the key generator and a finite set P including public information of the key generator, generates confidential key information s(x) of a receiver x from elements of a subset Sx of the confidential information S on a space determined by a subset Vx of the set S or P, and distributes the key information s(x) to the receiver x. A sender performs an operation of adding random numbers to elements in the public information corresponding to the elements of the set S and makes the multi-address transmission of a set R(P) including the elements which result from the operation. The receiver x selects a set R(P, x) of elements corresponding to Sx from R(P) to calculate a common key between the sender and the receiver from each element of R(P, x) and the confidential key information s(x). The common key corresponds to a data enciphered key.
According to a method for possessing a key in common with only receivers which belong to any set of receivers (in this case, a broadcasting station is a key generator and a sender), the broadcasting station generates confidential key information s(x) of a receiver x from a subset Sx of a finite set S including a plurality of elements and distributes the key information s(x) to the receiver x. The broadcasting station performs an operation of adding an arbitrarily selected random number to each element of a set P including values corresponding to the elements of the set S and makes the multi-address transmission of a set R(P) including the elements which result from the operation. The broadcasting station further transmits to only the limited receiver a value t(x) characteristic of the receiver x which corresponds to the confidential key information s(x) of the receiver x. The receiver x selects a set R(P, x) of elements corresponding to Sx from R(P) to calculate a common key between the broadcasting station and the receiver from the elements of R(P, x), the key information s(x) and the value t(x) of the receiver x.
In the following, mention will be made of a specific realizing example of a method in which the length of key distribution data is short even in the case of a large number of receivers and the security against the conspiracy attack of receivers is improved.
As a preparatory process, a key generator generates
P,Q:prime number
eixcex5Z,0 less than ei less than L=lcm(Pxe2x88x921, Qxe2x88x921)(1xe2x89xa6ixe2x89xa6m)
as confidential information of the key generator and generates
N=PQ
gixcex5Z, 0 less than gi less than N(1xe2x89xa6jxe2x89xa6n)
      u    ij    =            g      i              e        i              ⁢    mod    ⁢          xe2x80x83        ⁢    N    ⁢          xe2x80x83        ⁢          (                        1          ≤          i          ≤          m                ,                  1          ≤          j          ≤          n                    )      
n=kl, k,l( greater than 0)xcex5Z
as public information of the key generator.
Further, the key generator calculates Sx, (xcfx80, "sgr")=(Sx,xcfx801(1), . . . , Sx,xcfx801(h), . . . , Sx,xcfx80l(1), . . . , Sx, xcfx80l(h)) satisfying             ∑              j        =        1            h        ⁢                  S                  x          ,                                    π              i                        ⁡                          (              j              )                                          ⁢              e                              π            i                    ⁡                      (            j            )                                ≡      1    ⁢          (              mod        ⁢                  xe2x80x83                ⁢                  L                      σ            i                              )        ⁢          xe2x80x83        ⁢          (              1        ≤        i        ≤        l            )      
for xcfx80=(xcfx801, . . . , xcfx80l)xcex5Rk, n, "sgr"=("sgr"1, . . . , "sgr"l)xcex5Sk, n and distributes sx, (xcfx80,"sgr") as key information of a receiver x. Therein,       L          σ      ⁢              xe2x80x83            ⁢      i        =            ord      N        ⁢          (                        ∏                      j            =            1                    k                ⁢                  g                                    σ              i                        ⁢                          (              j              )                                          )        ⁢          xe2x80x83        ⁢                  (                  1          ≤          i          ≤          l                )            .      
Also, when "sgr"=("sgr"1, . . . , "sgr"l), "sgr"xe2x80x2=("sgr"1, . . . , "sgr"l)xcex5Sxe2x80x2k, n for set Rk, n={xcfx80=(xcfx801, . . . , xcfx80l)|one-to-one map xcfx80i: {1, 2, . . . , h)xe2x86x92(1, 2, . . . , m} (1xe2x89xa6ixe2x89xa6l, 1xe2x89xa6hxe2x89xa6m)}, set Sxe2x80x2k,n={"sgr"=("sgr"1, . . . , "sgr"l)|one-to-one map "sgr"1: A={1, 2, . . . , k}xe2x86x92B={1, 2, . . . , n} (1xe2x89xa6ixe2x89xa6l), "sgr"1 (A)U . . . U"sgr"l (A)=B}, a relation             σ      ~              σ        xe2x80x2              ⁢          ⟺      def        ⁢                  σ        i            (      A      )        =                    σ                  τ          ⁡                      (            i            )                          xe2x80x2            ⁡              (        A        )              ⁢          (              1        ≤        i        ≤        l            )      
is defined in regard to a proper permutation xcfx84 on a set {1, 2, . . . , l}. At this time, xe2x80x9cxcx9cxe2x80x9d represents an equivalent relation on Sxe2x80x2k,n and Sk,n is Sk,n=Sxe2x80x2k,n/xcx9c.
As a key distribution process,
(1) a sender randomly selects an integer r to calculate
yij=uijxcfx84mod N(1xe2x89xa6ixe2x89xa6m; 1xe2x89xa6jxe2x89xa6n)
from the public information with the object of sharing a common key K   K  =            ∏              i        =        1            n        ⁢                  g        i        r            ⁢      mod      ⁢              xe2x80x83            ⁢      N      
and makes the multi-address transmission of yij.
(2) The receiver x calculates the common key K in accordance with   K  =            ∏              i        =        1            l        ⁢                  ∏                  p          =          1                h            ⁢                        ∏                      q            =            1                    k                ⁢                              y                                                            π                  i                                ⁡                                  (                  p                  )                                            ⁢                              xe2x80x83                            ⁢                                                σ                  i                                ⁡                                  (                  q                  )                                                                    S                              x                ,                                                      π                    i                                    ⁡                                      (                    p                    )                                                                                ⁢          mod          ⁢                      xe2x80x83                    ⁢          N                    
wherein Z represents a set of the whole of integers, lcm(a,b) represents the lowest common multiple of integers a and b, and the least positive integer x satisfying gxxe2x89xa1l(mod N) for an integer N is represented by ordN (g).
According to the key distribution method of the present invention, the length of key distribution data can be reduced even in the case where the number of receivers is large. Also, even if unfair receivers club their confidential information, it is difficult to perform irregular practices. Therefore, the data distribution can be performed with a high efficiency and a high security.